package com.example.leetcode.interview.c0403;
/**
 * 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
 *
 *  
 *
 * 示例：
 *
 * 输入：[1,2,3,4,5,null,7,8]
 *
 *         1
 *        /  \
 *       2    3
 *      / \    \
 *     4   5    7
 *    /
 *   8
 *
 * 输出：[[1],[2,3],[4,5,7],[8]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/list-of-depth-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import com.example.leetcode.common.ListNode;
import com.example.leetcode.common.ListNodeWrapper;
import com.example.leetcode.common.TreeNode;
import com.example.leetcode.common.TreeNodeWrapper;

import java.util.*;

/**
 * 面试题 04.03. 特定深度节点链表
 * @author zhanpengguo
 * @date 2020-10-24 13:50
 */
public class Solution {

    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) {
            return null;
        }
        List<ListNode> ans = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(tree);
        while (!queue.isEmpty()) {
            ListNode head = null;
            ListNode tail = null;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                if (head == null) {
                    head = new ListNode(treeNode.val);
                    tail = head;
                } else {
                    tail.next = new ListNode(treeNode.val);
                    tail = tail.next;
                }
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
            ans.add(head);
        }
        ListNode[] res = new ListNode[ans.size()];
        return ans.toArray(res);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode treeNode = TreeNodeWrapper.stringToTreeNode("[]");
        ListNode[] listNodes = solution.listOfDepth(treeNode);
        for (ListNode listNode : listNodes) {
            ListNodeWrapper.prettyPrintLinkedList(listNode);
        }
    }
}
